﻿//https://leetcode.cn/problems/rotting-oranges/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    int cnt;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int ret;
public:
    int orangesRotting(vector<vector<int>>& grid)
    {
        int n = grid.size(), m = grid[0].size();
        ret = 0;
        cnt = 0;
        queue<pair<int, int>> q;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] == 1)
                {
                    cnt++;
                }
                else if (grid[i][j] == 2)
                {
                    q.push({ i,j });
                }
            }
        }

        while (q.size() && cnt)
        {
            ret++;
            int sz = q.size();
            for (int i = 0; i < sz; i++)
            {
                auto [x, y] = q.front();
                q.pop();
                for (int k = 0; k < 4; k++)
                {
                    int a = x + dx[k];
                    int b = y + dy[k];
                    if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 1)
                    {
                        cnt--;
                        q.push({ a,b });
                        grid[a][b] = 2;
                    }
                }
            }

        }
        return cnt ? -1 : ret;
    }
};
